package 华为OD机试真题2023.基础题;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HJ34_工作安排 {
  public static void main(String[] args) throws FileNotFoundException {
    Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/基础题/input/34.txt"));
    int W = in.nextInt();
    int N = in.nextInt();
    int[] weight = new int[N + 1];
    int[] value = new int[N + 1];
    for (int i = 1; i <= N; i++) {
      weight[i] = in.nextInt();
      value[i] = in.nextInt();
    }
    int[][] res = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= W; j++) {
        if (j >= weight[i]) {
          res[i][j] = Math.max(res[i - 1][j], res[i - 1][j - weight[i]] + value[i]);
        }
      }
    }
    System.out.println(res[N][W]);
  }
}
